Broadly speaking, there are two ways to find objects such as documents in a large collection: by search and by navigation. Searching involves specifying a query which a search engine will match against previously indexed objects, and return a hit-list of the best matching objects, possibly with an associated relevance score. The IBM SearchManager/2, a trademark of the IBM Corporation, is an example of such a system. The methods of indexing and searching for documents are well-known in the industry.
Navigation is possible if the objects have been previously organized into, e.g., a hierarchy. This organization will have been developed by categorizing the objects by selected criteria. Given such a system, the user typically finds an object by starting at a well-defined point such as the top of the hierarchy, and progressing down to levels of greater and greater specificity until a leaf-node category is reached, which contains just a few objects, where the desired one or ones can be found by inspection. In addition, systems can offer a combination of search and navigation. Yahoo (http://www.yahoo.com) is an example of such a system.
A categorization system takes an object such as a document and assigns to it one or more labels from a pre-defined set. The labels available correspond to the categories under consideration.
The categories form a way of grouping objects that are similar according to one or more criteria. For example, the set of categories might correspond to the language a document is written in. The label for a category, and for documents in that category, will be the name of the language. World-Wide-Web search engines such as AltaVista (http://www.altavista.digital.com) associate a language tag with every document returned in a hit list. These tags were assigned by an automatic process.
Another useful categorization scheme is by subject-matter. Yahoo has categorized several hundred thousand documents into tens of thousands of categories, although this process was done by hand. However, to keep track of huge collections such as the World-Wide-Web, or to develop navigation systems for company intranets or other domains, categorizing automatically is of increasing importance.
There are several different methods to perform categorization: two will be described here in the context of text document categorization. All methods require a set of categories, and a set of previously categorized objects, for training. The so-called `centroid` or `vector-space` method works as follows. A feature-selector program is used to extract interesting qualities from the documents. These features are usually words, possibly with common words or `stop-words` (such as `the`, `of`, etc.) filtered out. For each category, a vector is generated from the documents assigned to that category. The positions in the vector correspond to the features, the value at a given position the number of occurrences of the feature in the set of documents making up the category. A similar such vector is generated for the document to be categorized. Then for each category, the `cosine-distance` is calculated between the category vector and the test document vector. The cosine-distance is the scalar product of the two vectors divided by the product of the vector magnitudes; it is also equal to the cosine of the angle between the vectors in n-space. Since it is a cosine, it falls in the range 0-1, where 0 represents orthogonality and 1 exact correspondence. In this way, the system generates a hit-list of categories with matching scores. For a description of vector-space methods in Information Retrieval, see G. Salton, "Automatic Text Processing: The Transformation, Analysis and Retrieval of Information by Computer", Addison-Wesley, Reading, Pa., 1989.
Another common method is the KNN, or K-nearest-neighbor method. In this method the document to be categorized is treated as a query to a search engine, whose index is generated from all of the documents in the categorizer's training set. The hit-list generated here is the list of the best-matching documents to the one in question. The top K documents from this list are selected. Since each document is part of the training set, it has been assigned to one or more categories. Hence each document imparts a `vote` to each category it belongs to. This vote may be weighted by unity or by the relevance score returned by the search engine. In any case, the total number of votes received by each category is tallied, and used to provide the category hit-list.
Given the category hit-list, systems usually employ one of the following techniques for purposes of committing category assignments to the document: 1) the top category is selected, 2) the top m categories are selected, for some pre-defined constant m, 3) all categories which have a score greater than a threshold t are selected, and 4) the top category plus any categories which have a score greater than a threshold t are selected.
If relevance ranking values are considered to be probabilities, then the confidence one has in their correctness can be computed by standard probability theory, as found in any standard text book on Probability Theory--see for example W. Feller "An Introduction to Probability Theory and its Applications", John Wiley & Sons, Inc., 1950. Alternatively, the values can be treated as evidence, and the appropriate theory is the Dempster-Shafer Theory of Evidence (see: Shafer, G., "Perspectives on the Theory and Practice of Belief Functions", International Journal of Approximate Reasoning, Vol 4, Elsevier 1990, pp 323-363.).